import javax.swing.tree.TreeNode;
import java.util.*;

public class TestBinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用

    public TreeNode(char val){
        this.val=val;
    } }

    public TreeNode createTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;
        return A;
    }


    //前序遍历(递归）
    public void preOrder(TreeNode root){
        if (root==null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //前序遍历（非递归）
    public void preOrder2(TreeNode  root){
        Stack<TreeNode>stack=new Stack<>();
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                System.out.print(cur.val+" ");//当cur不为空的时候才把他打印下来
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            cur=top.right;
        }
    }
    //中序遍历（非递归）
    public void inOrder2(TreeNode root){
        Stack<TreeNode>stack=new Stack<>();
        TreeNode cur=root;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            System.out.print(top.val+" ");
            cur=top.right;//打印之后找右边的,cur为空就弹栈,不为空就继续遍历cur
        }
    }
    //后序遍历（非递归）
    public void postOrder2(TreeNode root){
        Stack<TreeNode>stack=new Stack<>();
        TreeNode cur=root;
        TreeNode pre=null;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);//当cur不为空就压栈然后往左走
                cur=cur.left;
            }
            TreeNode top=stack.peek();//找到根,不能像前序和中序那样直接弹出,因为根最后打印
            if (top.right==null||top.right==pre){//top.right==pre是判断这个节点是否被打印过了
                stack.pop();//如果右边为空或者右边被打印过了就打印当前这个根
                System.out.print(top.val+" ");
                pre=top;//记录每一次打印过的值
            }else {//右边不为空就去递归右
                cur=top.right;
            }
        }
    }
    //中序遍历
    public void inOrder(TreeNode root){
        if (root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    //后序遍历
    public  void postOrder(TreeNode root){
    if (root==null){
        return;
    }
    postOrder(root.left);
    postOrder(root.right);
        System.out.print(root.val+" ");
    }
    //直接递归获取节点个数
    public  int size(TreeNode root){
        if(root==null){
            return 0;
        }
        int ret=size(root.left)+size(root.right)+1;
        return ret;
    }
    //方法二求节点个数
     public  int nodeSize;//static修饰的东西不用创建对象就可以调出来，不同的对象调用static都是同一个
    public void size2(TreeNode root){

        if (root==null){
            return;//如果自己为空就返回，自己不为空就nodeSize++，所以得出来是节点个数
        }
        nodeSize++;
        size2(root.left);
        size2(root.right);


    }
    //求叶子结点的个数
     public int getLeafNodeCount(TreeNode root){
        if (root==null){
            return 0;
        }
        if (root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
     }
     public int leafsize;
    public void getLeafNodeCount2(TreeNode root) {
        if (root == null) {
            return ;
        }
        if (root.left == null && root.right == null) {
        leafsize++;

        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);//遍历
    }
//判断第k层有多少个节点
    public int getLevelNodeCount(TreeNode root,int k){
        if (root==null){
            return 0;

        }
        if (k==1){
            return 1;
        }
        return getLevelNodeCount(root.left,k-1)+getLevelNodeCount(root.right,k-1);
    }
    ////求树的高度
    public int getHeight(TreeNode root){
        if (root==null){
            return 0;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return leftHeight>rightHeight?
                leftHeight+1:rightHeight+1;
    }
    //找到节点位置
    public   TreeNode find(TreeNode root,char val){
        if (root==null){
            return null;
        }
        if(root.val==val){
            return root;//找自己
        }
        TreeNode ret=find(root.left,val);//如果找到了就返回root，没找到返回null，都给ret
        if (ret!=null){//接收到的值要么为空要么是我要找的
            return ret;//找左边
        }

         ret=find(root.right,val);
        if (ret!=null){
            return ret;//找右边
        }

        return null;//如果左右两边都没有找到返回null
    }
    //检验两个二叉树是否相同（结构和值）时间复杂度是m，n的最小值
    public boolean isSameTree(TreeNode p,TreeNode q) {
        if (p != null && q == null || p == null && q != null) {
            return false;
        }
        if (p == null && q == null) {
            return false;
        }
        if (q.val != p.val) {
            return false;
        }
        return isSameTree(p.left, q.left)
                && isSameTree(p.right, q.right);
        //上面把当前节点不相等的情况排查完了，
        // 到这里证明当前节点相同，所以只有左右节点都相同才满足条件
    }
    //判断一个树是否是另一个树的子树(时间复杂度m*n）
    public boolean isSubtree(TreeNode root,TreeNode subRoot){
        if (root==null){
            return false;
        }
        if (isSameTree(root,subRoot)){
            return true;//看自己是否和subRoot相同
        }
        if (isSubtree(root.left,subRoot)){
            return true;//看左树是否包含subRoot
        }
        if (isSubtree(root.right,subRoot)){
            return true;////看右树是否包含subRoot
        }
        return false;//如果都没有只能返回false了
    }
    //翻转树，除了根节点，最后return根节点
    public TreeNode invertTree(TreeNode root){
        if (root==null){
            return null;//碰到null就返回上一层就不翻转了
        }
        if (root.left==null&&root.right==null){
            return root;//如果是叶子节点省的交换下一个
        }
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
//判断是否是平衡二叉树（子树深度相差不能超过1），所有节点的深度相差不能超过1（需要借助maxDept2（））
    //我们用时间复杂度为o1的方法，从下往上只要有不合适的就返回-1，然后一直返回-1
    public  boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return maxDept2(root)>=1;//返回-1代表肯定不是平衡树
    }
    public int maxDept2(TreeNode root){//其实是求最大深度，如果返回-1，代表不是平衡树
        if (root==null){
            return 0;
        }
        int leftHeight=maxDept2(root.left);
        if (leftHeight<0){//在这里就截断了，左树不满足条件返回-1，如果左树=-1根直接返回-1
            return -1;//如果左树小于0root直接返回-1；
        }
        int rightHeight=maxDept2(root.right);
        if (rightHeight<0){
            return -1;
        }
        if (Math.abs(leftHeight-rightHeight)<=1){
            return Math.max(leftHeight,rightHeight)+1;//如果满是平衡树就返回树的深度
        }else {
            return -1;//如果不满足平衡树的条件就返回-1；-1才是我不满足的条件
        }
    }
    //判断一棵树是否是对称二叉树
    public boolean isSymmetric(TreeNode root){

        if (root==null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);//把左右节点扔过去比较，不管根节点
    }

        public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){

        //一个为空一个不为空的情况(结构都不相同）
        if (leftTree!=null&&rightTree==null||
                leftTree==null&&rightTree!=null){
            return false;
        }
        //两个都为空
        if (leftTree==null&&rightTree==null){
            return  true;
        }
        //两个里面都有值
        if (leftTree.val!=rightTree.val){
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right)&&isSymmetricChild(leftTree.right,rightTree.left);
    }



    //传入一个先序遍历的字符串让其中序遍历的方式输出
    public int i=0;
    public TreeNode createTree1(String str){
        TreeNode root=null;
        if (str.charAt(i)!='#'){
            root=new TreeNode(str.charAt(i));
            i++;
            root.left=createTree1(str);
            root.right=createTree1(str);
        }else {
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        TestBinaryTree testBinaryTree=new TestBinaryTree();
        Scanner inn=new Scanner(System.in);

            String str=inn.nextLine();
            TreeNode root= testBinaryTree.createTree1(str);
            testBinaryTree.inOrder(root);

    }
    //层序遍历
    public void levelOrder(TreeNode root){//用队列来实现
        Queue<TreeNode>queue=new LinkedList<>();
        if (root==null){
            return;
        }
        queue.offer(root);
        while (!queue.isEmpty()){//这里是对象，得用方法，因为对象里面就算没值了，也不为空，因为里面存的是空值
            TreeNode cur= queue.poll();
            System.out.print(cur.val+" ");
            if (cur.left!=null) {
                queue.offer(cur.left);
            }
            if (cur.right!=null){
                queue.offer(cur.right);
            }
        }}
    //是否是完全二叉树
    public boolean isCompareTree(TreeNode root){
        //用层序遍历的方法，不同的是空节点也放进队列里面，只要碰到null，
        // 判断队列里面剩下的元素如果全为空就是完全二叉树
       Queue<TreeNode>queue=new LinkedList<>();
       if (root==null)return true;
       queue.offer(root);
       while (!queue.isEmpty()){
        TreeNode cur=queue.poll();
        if (cur==null){
            break;
        }
        queue.offer(cur.left);
        queue.offer(cur.right);
       }
       while (!queue.isEmpty()){
           TreeNode node= queue.peek();
           if (node!=null){
               return false;
           }else {
               queue.poll();
           }

       }
       return true;
    }
    //分层遍历输出
    public List<List<Character>> levelOrder2(TreeNode root){//返回一个二维数组
        List<List<Character>> ret=new ArrayList<>();//创建一个二维数组

        if (root==null){
            return ret;}
          Queue<TreeNode>queue=new LinkedList<>();//创建一个队列
            queue.offer(root);
            while (!queue.isEmpty()){
                int size=queue.size();
                List<Character>list=new ArrayList<>();
                while (size>0){
                    TreeNode cur=queue.poll();
                    list.add(cur.val);
                    if (cur.left!=null){
                        queue.offer(cur.left);
                    }
                    if (cur.right!=null){
                        queue.offer(cur.right);
                    }
                size--;
                }
                ret.add(list);
            }
            return ret;
        }
//求一棵树的最近公共祖先
    //方法一
    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
        if (root==null){
            return  null;
        }
        if (root==p||root==q){
            return root;//如果碰到我要找的其中一个就返回他
        }
        TreeNode leftTree=lowestCommonAncestor(root.left,p,q);//去找左边
        TreeNode rightTree=lowestCommonAncestor(root.right,p,q);//找右边
        if (leftTree!=null&&rightTree!=null){//因为层层递归的关系，哪个左右都不为空就返回它
            return  root;
        }else if (leftTree!=null){
            return leftTree;
        }else {
            return rightTree;//如果左右都为空，到这了，不影响返回空
        }
    }
    //方法二
    public  TreeNode lowestCommonAncestor2(TreeNode  root,TreeNode p,TreeNode q){
        if (root==null){
            return root;
        }
        Stack<TreeNode>stackP=new Stack<>();
        Stack<TreeNode>stackQ=new Stack<>();
        getPath(root,p,stackP);
        getPath(root,q,stackQ);
        int sizeP=stackP.size();
        int sizeQ=stackQ.size();
        if(sizeP>sizeQ){
            int size=sizeP-sizeQ;
            while (size>0){
                stackP.pop();
                size--;
            }
        }else {
            int size=sizeQ-sizeP;
            while (size>0){
                stackQ.pop();
                size--;
        }
    }
    while (!stackP.isEmpty()&&!stackQ.isEmpty()){
        if (stackP.peek()==stackQ.peek()){
            return stackP.peek();
        }else {
            stackP.pop();
            stackQ.pop();
        }
    }
    return null;
    }
    public boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode>stack){
        //得到root到node的路径
        if (root==null){
            return false;
        }
        stack.push(root);//先压进来
        if (root==node){
            return true;
        }
        boolean flg1=getPath(root.left,node,stack);
        if (flg1==true){//root的左右树只要有一个符合条件，root就返回true
            return true;
        }
        boolean flg2=getPath(root.right,node,stack);
        if (flg2==true){
            return  true;
        }
        stack.pop();//如果上面都没有返回，证明不符合条件，弹出，返回false
        return false;
    }
//给出前序和中序,创建二叉树
   //创建树的时候是从高的地方往底层创建,但是返回时把底层返回完了,再返回高层的,左树执行完了再执行右树,因为满足递归的规律
        public int preindex;//要把preindex写成全局变量
    public TestBinaryTree.TreeNode buildTree(char[]preorder, char[]inorder, int inBegin,int inEnd){
        //preorder是输入的前序遍历的数组,inorder是输入的中序遍历的数组
        //preindex是前序数组定位到的下标, inBegin和inEnd是创建二叉树管辖的始末的下标
        //inbegin和inend围着中序数组的那部分是要递归的树
        if(inBegin>inEnd){
            return null;
        }
        TestBinaryTree.TreeNode root=new TestBinaryTree.TreeNode(preorder[preindex]);
        int rootIndex=findRootIndex(inorder,inBegin,inEnd,preorder[preindex]);
        preindex++;
        System.out.println(root.val);;
        System.out.println();
        System.out.println(inorder+" ----" + preorder + " ---------"+ "-----"+(rootIndex+1) +"---------"+inEnd);
        root.left=buildTree(preorder,inorder,inBegin,rootIndex-1);//切割左树
        // rootindex是局部变量,同一层函数的rootindex是一样的(同理inbegin和inend也一样)
        //在每一次有新的root时以自己为依据,为自己的左右子树划分空间,也就是inbegin和inend所管辖的范围
        root.right=buildTree(preorder,inorder,rootIndex+1,inEnd);//切割右树
        return root;
    }
    public  int findRootIndex(char[]inorder,int inBegin,int inEnd,char key){//找到右树中根节点的下标
        for(int i=inBegin;i<=inEnd;i++){
            if (inorder[i]==key){
                return i;
            }
        }
        return  -1;
    }
        //给出后序和中序创建二叉树
         //你这不是参数传递过来的吗 你放外面访问不了 你得放到里面
    //你这代码没办法这么写作为全局变量 写不成 除非你提前直到这个length是多少 写死在这比如  否则现在这样写不了 理解吗
    int postIndex = 7;
    public TreeNode buildTree2(char []postOrder,char[]inOrder,int inBegin,int inEnd){

        if (inBegin>inEnd){
            return null;
        }
        if(postIndex < 0){
            return null;
        }
        TestBinaryTree.TreeNode root=new TestBinaryTree.TreeNode(postOrder[postIndex]);
        //你这参数类型也不对呀 参数类型是TreeNode 而你传参是int
        int rootIndex=findRootIndex(inOrder,inBegin,inEnd,postOrder[postIndex]);
        postIndex--;
        root.right=buildTree2(postOrder,inOrder,rootIndex+1,inEnd);//先构建右树,因为左右根的顺序,根建好了,递归的下一个根是右树
        root.left=buildTree2(postOrder,inOrder,inBegin,rootIndex-1);
        return root;
    }


}










